#include "list.h"
#include "../debug.h"

static bool is_sorted(struct list_elem *a, struct list_elem *b,
                      list_less_func *less, void *aux) UNUSED;

static inline bool
is_head(struct list_elem *elem) {
    return elem != NULL && elem->prev == NULL && elem->next != NULL;
}

static inline bool
is_interior(struct list_elem *elem) {
    return elem != NULL && elem->prev != NULL && elem->next != NULL;
}

static inline bool
is_tail(struct list_elem *elem) {
    return elem != NULL && elem->prev != NULL && elem->next == NULL;
}

void
list_init(struct list *list) {
    ASSERT (list != NULL);
    list->head.prev = NULL;
    list->head.next = &list->tail;
    list->tail.prev = &list->head;
    list->tail.next = NULL;
}

struct list_elem *
list_begin(struct list *list) {
    ASSERT (list != NULL);
    return list->head.next;
}

struct list_elem *
list_next(struct list_elem *elem) {
    ASSERT (is_head(elem) || is_interior(elem));
    return elem->next;
}

struct list_elem *
list_end(struct list *list) {
    ASSERT (list != NULL);
    return &list->tail;
}

struct list_elem *
list_rbegin(struct list *list) {
    ASSERT (list != NULL);
    return list->tail.prev;
}

struct list_elem *
list_prev(struct list_elem *elem) {
    ASSERT (is_interior(elem) || is_tail(elem));
    return elem->prev;
}

struct list_elem *
list_rend(struct list *list) {
    ASSERT (list != NULL);
    return &list->head;
}

struct list_elem *
list_head(struct list *list) {
    ASSERT (list != NULL);
    return &list->head;
}

struct list_elem *
list_tail(struct list *list) {
    ASSERT (list != NULL);
    return &list->tail;
}

void
list_insert(struct list_elem *before, struct list_elem *elem) {
    ASSERT (is_interior(before) || is_tail(before));
    ASSERT (elem != NULL);

    elem->prev = before->prev;
    elem->next = before;
    before->prev->next = elem;
    before->prev = elem;
}

void
list_splice(struct list_elem *before,
            struct list_elem *first, struct list_elem *last) {
    ASSERT (is_interior(before) || is_tail(before));
    if (first == last)
        return;
    last = list_prev(last);

    ASSERT (is_interior(first));
    ASSERT (is_interior(last));

    first->prev->next = last->next;
    last->next->prev = first->prev;

    first->prev = before->prev;
    last->next = before;
    before->prev->next = first;
    before->prev = last;
}

void
list_push_front(struct list *list, struct list_elem *elem) {
    list_insert(list_begin(list), elem);
}

void
list_push_back(struct list *list, struct list_elem *elem) {
    list_insert(list_end(list), elem);
}

struct list_elem *
list_remove(struct list_elem *elem) {
    ASSERT (is_interior(elem));
    elem->prev->next = elem->next;
    elem->next->prev = elem->prev;
    return elem->next;
}

struct list_elem *
list_pop_front(struct list *list) {
    struct list_elem *front = list_front(list);
    list_remove(front);
    return front;
}

struct list_elem *
list_pop_back(struct list *list) {
    struct list_elem *back = list_back(list);
    list_remove(back);
    return back;
}

struct list_elem *
list_front(struct list *list) {
    ASSERT (!list_empty(list));
    return list->head.next;
}

struct list_elem *
list_back(struct list *list) {
    ASSERT (!list_empty(list));
    return list->tail.prev;
}

size_t
list_size(struct list *list) {
    struct list_elem *e;
    size_t cnt = 0;

    for (e = list_begin(list); e != list_end(list); e = list_next(e))
        cnt++;
    return cnt;
}

bool
list_empty(struct list *list) {
    return list_begin(list) == list_end(list);
}

static void
swap(struct list_elem **a, struct list_elem **b) {
    struct list_elem *t = *a;
    *a = *b;
    *b = t;
}

void
list_reverse(struct list *list) {
    if (!list_empty(list)) {
        struct list_elem *e;

        for (e = list_begin(list); e != list_end(list); e = e->prev)
            swap(&e->prev, &e->next);
        swap(&list->head.next, &list->tail.prev);
        swap(&list->head.next->prev, &list->tail.prev->next);
    }
}

static bool
is_sorted(struct list_elem *a, struct list_elem *b,
          list_less_func *less, void *aux) {
    if (a != b)
        while ((a = list_next(a)) != b)
            if (less(a, list_prev(a), aux))
                return false;
    return true;
}

static struct list_elem *
find_end_of_run(struct list_elem *a, struct list_elem *b,
                list_less_func *less, void *aux) {
    ASSERT (a != NULL);
    ASSERT (b != NULL);
    ASSERT (less != NULL);
    ASSERT (a != b);

    do {
        a = list_next(a);
    } while (a != b && !less(a, list_prev(a), aux));
    return a;
}

static void
inplace_merge(struct list_elem *a0, struct list_elem *a1b0,
              struct list_elem *b1,
              list_less_func *less, void *aux) {
    ASSERT (a0 != NULL);
    ASSERT (a1b0 != NULL);
    ASSERT (b1 != NULL);
    ASSERT (less != NULL);
    ASSERT (is_sorted(a0, a1b0, less, aux));
    ASSERT (is_sorted(a1b0, b1, less, aux));

    while (a0 != a1b0 && a1b0 != b1)
        if (!less(a1b0, a0, aux))
            a0 = list_next(a0);
        else {
            a1b0 = list_next(a1b0);
            list_splice(a0, list_prev(a1b0), a1b0);
        }
}

void
list_sort(struct list *list, list_less_func *less, void *aux) {
    size_t output_run_cnt;

    ASSERT (list != NULL);
    ASSERT (less != NULL);

    do {
        struct list_elem *a0;
        struct list_elem *a1b0;
        struct list_elem *b1;

        output_run_cnt = 0;
        for (a0 = list_begin(list); a0 != list_end(list); a0 = b1) {
            output_run_cnt++;

            a1b0 = find_end_of_run(a0, list_end(list), less, aux);
            if (a1b0 == list_end(list))
                break;
            b1 = find_end_of_run(a1b0, list_end(list), less, aux);

            inplace_merge(a0, a1b0, b1, less, aux);
        }
    } while (output_run_cnt > 1);

    ASSERT (is_sorted(list_begin(list), list_end(list), less, aux));
}

void
list_insert_ordered(struct list *list, struct list_elem *elem,
                    list_less_func *less, void *aux) {
    struct list_elem *e;

    ASSERT (list != NULL);
    ASSERT (elem != NULL);
    ASSERT (less != NULL);

    for (e = list_begin(list); e != list_end(list); e = list_next(e))
        if (less(elem, e, aux))
            break;
    return list_insert(e, elem);
}

void
list_unique(struct list *list, struct list *duplicates,
            list_less_func *less, void *aux) {
    struct list_elem *elem, *next;

    ASSERT (list != NULL);
    ASSERT (less != NULL);
    if (list_empty(list))
        return;

    elem = list_begin(list);
    while ((next = list_next(elem)) != list_end(list))
        if (!less(elem, next, aux) && !less(next, elem, aux)) {
            list_remove(next);
            if (duplicates != NULL)
                list_push_back(duplicates, next);
        } else
            elem = next;
}

struct list_elem *
list_max(struct list *list, list_less_func *less, void *aux) {
    struct list_elem *max = list_begin(list);
    if (max != list_end(list)) {
        struct list_elem *e;

        for (e = list_next(max); e != list_end(list); e = list_next(e))
            if (less(max, e, aux))
                max = e;
    }
    return max;
}

struct list_elem *
list_min(struct list *list, list_less_func *less, void *aux) {
    struct list_elem *min = list_begin(list);
    if (min != list_end(list)) {
        struct list_elem *e;

        for (e = list_next(min); e != list_end(list); e = list_next(e))
            if (less(e, min, aux))
                min = e;
    }
    return min;
}
